package io.vector.study.algorithm.heap;

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * Created by vector on 2017/3/15.
 */
public abstract class AbstractHeap<E extends Comparable<? super E>> implements Heap<E> {

    // use ArrayList support auto increase, if user array, need increase manually
    private List<E> elements;

    private static final int DEFAULT_CAPACITY = 10;

    public AbstractHeap() {
        this(DEFAULT_CAPACITY);
    }

    public AbstractHeap(int capacity) {
        this.elements = new ArrayList<E>(capacity);
    }

    @Override
    public void add(E e) {
        this.elements.add(e);
        percolateUp(this.elements.size() - 1);
    }

    protected abstract void percolateUp(int index);

    @Override
    public E peek() {
        if (this.elements.isEmpty()) {
            throw new NoSuchElementException();
        }
        return this.elements.get(0);
    }

    @Override
    public E pop() {
        E top = peek();
        if (!isEmpty()) {
            int lastIndex = size() - 1;
            this.elements.set(0, this.elements.get(lastIndex));
            this.elements.remove(lastIndex);
            percolateDown(0);
        }
        return top;
    }

    protected abstract void percolateDown(int index);

    @Override
    public boolean isEmpty() {
        return size() == 0;
    }

    @Override
    public void clear() {
        this.elements.clear();
    }

    @Override
    public int size() {
        return this.elements.size();
    }

    @Override
    public E[] toArray() {
        return (E[]) this.elements.toArray(new Comparable[size()]);
    }

    protected int parentIndex(int index) {
        return (int) Math.floor(index - 1);
    }

    protected int leftChildIndex(int index) {
        return 2 * index + 1;
    }

    protected int rightChildIndex(int index) {
        return leftChildIndex(index) + 1;
    }

    protected void swap(int index1, int index2) {
        if (!isValidIndex(index1) || !isValidIndex(index2)) {
            throw new IndexOutOfBoundsException();
        }

        if (index1 == index2) {
            return ;
        }

        E temp = this.elements.get(index1);
        this.elements.set(index1, this.elements.get(index2));
        this.elements.set(index2, temp);
    }

    protected int compareByIndex(int index1, int index2) {
        if (!isValidIndex(index1) || !isValidIndex(index2)) {
            throw new IndexOutOfBoundsException();
        }

        if (index1 == index2) {
            return 0;
        }
        return this.elements.get(index1).compareTo(this.elements.get(index2));
    }

    protected boolean isValidIndex(int index) {
        return index >= 0 && index < this.elements.size();
    }

    protected boolean hasChild(int index) {
        return leftChildIndex(index) < size();
    }

    protected boolean hasParent(int index) {
        return parentIndex(index) >= 0;
    }

}
